Bandwidth limitations in various data transmitting media have led to the development of methods for "compressing" data. Compression generally refers to the representation of a set of data by using fewer elements than contained in the set to represent the set of data. If each data element within the set may be regenerated from the compressed representation then the method is commonly known as lossless. If the data representation regenerated from the compressed representation of the data set does not accurately represent each and every element within it, the method is known as lossy. Because the set of compressed data may represent all elements but contain fewer elements than the actual set represented, the transmission of the compressed data usually requires less time and fewer resources than if the original set of data was transmitted. Conversion of the transmitted compressed data set is called decompression and is usually performed by a receiver to obtain the original data set or a close approximation thereto. Thus, the compressed data must not only be capable of accurately representing the data set, but it must also contain sufficient information for the receiver to decompress the data representation.
One known method for compressing a data set uses a data set transformation function to represent a data set. The data set transformation function may be constructed out of projective, affine or complex mapping functions that, when applied to any data set in iterative fashion, converges to the same attractor. As a result, the coefficients of the data set transformation function may be used to represent a data set that is substantially the same as the attractor. This type of compression method is known as an iterated function system or IFS. This type of compression method is lossy as the attractor usually approximates the data set and does not exactly reproduce the data set.
One lossless compression method which uses iterated function systems is disclosed in Fractal Image Compression by Michael F. Barnsley and Lyman P. Hurd, AK Peters Ltd., 1992. The section entitled Arithmetic Compression and IFS Fractals discusses the use of iterated function systems to encode a datastream from a zero-order Markov source. To generate the mapping functions used to compress the data from such a source, a sample datastream is collected from the data source and the frequency of occurrence for each symbol in the datastream is computed. These frequencies are then used to find the coefficients for a mapping transformation having the general form: EQU w.sub.i (x)=p.sub.i x+t.sub.i for i =1,2, . . . ,n
where the p.sub.i for i=1,2, . . . ,n are independent probabilities for each of the symbols in the datastream. The mapping transformations computed from the representative datastream are then used to compress subsequent datastreams from the zero-order Markov source and the mapping transformations are utilized to construct a decompressor as well.
While the compressor/decompressor combination for this zero-order Markov process compresses datastreams for this type of source, it fails to efficiently compress data from higher order Markov sources or other stochastic processes in which the generation of the symbols are not truly independent. Specifically, most data communicated between systems today are not independently generated streams of the binary symbols 1 and 0. Rather, there is a long term correlation between the binary representation of the words, for example, in a word processing program as most of the documents generated by a particular word processing program are written in a particular language, say English. As a result, the output of that program would tend to have certain words reoccurring on a regular basis. Because the system described above views the generation of the symbols as being completely independent, the correlation between the frequency of occurrence of the symbols is not used to more efficiently compress the datastreams generated by such stochastic processes.
What is needed is a lossless method of compression using iterated function systems which efficiently encode and decode datastreams for stochastic processes in a way which incorporates the long term data correlation for such sources.